Optimal service selection satisfying Service Level Agreement (SLA) is a NP hard problem. In order to solve the dimension and granularity problems, a comprehensive service selection model was proposed which considered semantic link degree, Quality of Service (QoS) and transactional properties. A coding strategy was adopted to solve the multi-granularity problem. In order to reduce the computation cost, a hybrid optimization algorithm based on clonal selection and Genetic Algorithm (GA) was proposed. Firstly, the dynamic fitness function was adopted to drive the evolution toward constraint satisfaction. Secondly, the knowledge-oriented crossover and mutation operators based on priority were designed to ensure the transactional property of composite service. Finally, the clonal selection was combined into the GA to improve the search ability. In the simulation experiments, the proposed algorithm had better performance in accuracy and successful rate compared to GA; the time cost of the proposed algorithm was a little higher than that of GA but much lower than that of exhaustive search algorithm. The experimental results show that the proposed algorithm can guarantee QoS of service selection with low time cost.